/**
 * KMP.java 
 * 
 * Klasa odpowiedzialna za poprawne wyszukanie zadanego wyrazu w pozostałych wyrazach.
 * Klasa wykorzystuje algorytm Knutha-Morrisa-Pratta oraz mechanizm funkcji postfiksowej.
 *
 * @author Mateusz Grzechociński
 *		   mateusz@grzechocinski.net
 *
 * @date 2006-12-17, 22:12:18
 */
package net.grzechocinski.wordcounter.KMP;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class KMP {

	public static List<WordObject> countInOtherOccurrences(List<WordObject> array) {

		for (WordObject pattern : array) {
			for (WordObject text : array) {
				check(text,pattern,calculate_p(text));						
			}
		}
		return array;		
	}

	/**
	 * Metoda wyszukujaca wzorzec pattern w tekscie text
	 *
	 * @param pattern wzor ktorzego szukamy
	 * @param text slowo w ktorym szukamy wzoru
	 * @param p tablica wartosci funkcji postfiksowej dla danego wzorca
	 */
	private static void check(WordObject pattern, WordObject text,int[] postfix){
		int pLength=pattern.getWord().length();
		int tLength=text.getWord().length();

		String p = pattern.getWord().toLowerCase();
		String t = text.getWord().toLowerCase();
		int q=0;  //ile znakow sie powtarza

		//ignoruj wzory dluzsze od tekstu oraz wzory jednoliterowe
		if(tLength>pLength && pLength>1){

			//szukaj od pierwszego znaku
			for(int i=0; i<tLength; i++){

				while(q>0 && p.charAt(q) != t.charAt(i))
					q=postfix[q-1];   //ile wczesniejszych literek sie powtarzalo

				//ile znak sie powtarza, zwieksz licznik
				if(p.charAt(q)==t.charAt(i))
					q++;

				//to jest to slowo!
				if(q == pLength){
					q=postfix[q-1];
					pattern.incrementInOtherCounter();
				}
			}
		}
	}


	/**
	 * Metoda wyliczajaca tablice wartosci funkci postfiksowej
	 *
	 * @param pattern slowko wzorcowe
	 * @return postfix[] tablica wartosci funkcji postfiksowej
	 */
	private static int [] calculate_p(WordObject pattern){
        int pLength=pattern.getWord().length();
        int postfix[]= new int[pLength];    	  //tablica wartosci f.postfiksowej
        int pVal=0;						  		  //wartosc f-cji postfiksowej

        postfix[0]=0; //pierwsza literka nie moze byc swoim sufiksem
        String p = pattern.getWord().toLowerCase();

        //sprawdzaj sufiks od drugiej literki
        for(int i=1; i<pLength; i++){

            while(pVal>0 && p.charAt(pVal) != p.charAt(i))
                pVal=postfix[pVal];

            if(p.charAt(pVal)==p.charAt(i))
                pVal++;

            postfix[i]=pVal;
        }

        return postfix;
    }
}
